#include <cstdio>
#include <cstring>

struct Matrix
{
    int n, m, a[ 4 ][ 4 ];
};

void operator *= ( Matrix &a, const Matrix &b )
{
    Matrix c;
    int i, j, k;
    c.n = a.n; c.m = b.m;
    for ( i = 0; i < c.n; i++ )
        for ( j = 0; j < c.m; j++ )
            for ( c.a[ i ][ j ] = k = 0; k < a.m; k++ )
                c.a[ i ][ j ] = ( c.a[ i ][ j ] + a.a[ i ][ k ] * b.a[ k ][ j ] ) % 10007;
    a = c;
}

int main( )
{
    int n, p, i, j;
    Matrix a, b, c;
    while ( scanf("%d", &n) != EOF )
    {
        a.n = 1; a.m = 3;
        a.a[ 0 ][ 0 ] = 0; a.a[ 0 ][ 1 ] = 2; a.a[ 0 ][ 2 ] = 0;
        b.n = b.m = c.n = c.m = 3;
        memset( b.a, 0, sizeof( b.a ) );
        b.a[ 0 ][ 0 ] = b.a[ 1 ][ 1 ] = b.a[ 2 ][ 2 ] = 1;
        c.a[ 0 ][ 0 ] = 2; c.a[ 0 ][ 1 ] = c.a[ 0 ][ 2 ] = c.a[ 1 ][ 0 ] = c.a[ 2 ][ 2 ] = 0;
        c.a[ 1 ][ 1 ] = c.a[ 1 ][ 2 ] = c.a[ 2 ][ 0 ] = c.a[ 2 ][ 1 ] = 1;
        if ( n == 0 )
        {
            puts("0");
            continue;
        }
        n--; p = 1;
        while ( p <= n ) p <<= 1;
        p >>= 1;
        while ( p > 0 )
        {
            b *= b;
            if ( p & n )
                b *= c;
            p >>= 1;
        }
        a *= b;
        printf("%d\n", a.a[ 0 ][ 0 ]);
    }
    return 0;
}
